#pragma once

#include "Common.hpp"
#include <unordered_map>
#include <memory>

class PageCache // 饿汉的单例模式
{
public:
    static PageCache *GetInstance()
    {
        return &_instance;
    }
    Span *NewSpan(size_t k /*k表示要申请的页数*/)
    {
        cout << "debug PageCache::NewSpan begin" << endl;
        // assert(k > 0 && k < PAGE_NUM - 1);
        assert(k > 0); // 优化后的

        // 申请的空间超过128页
        if (k >= PAGE_NUM - 1)
        {
            // cout << "k > PageNum" << endl;
            // 用SystemAlloc向OS申请k页内存
            void *ptr = SystemAlloc(k);

            // Span* span = new Span;
            // 用定长内存池取代new
            Span *span = _span_pool.New();

            // 利用上面得到的空间对这个span进行初始化
            span->_n = k;
            span->_page_id = ((PageID)ptr) >> PAGE_SHIFT;

            // 构建映射关系
            //  _id_span_map.set[span->_page_id] = span;
            _id_span_map.set(span->_page_id, span);

            // cout << "suc" << endl;
            return span;
        }

        // cout << "debug PageCache NewSpan begin" << endl;
        // 分为三种情况：
        // 1、k号桶上的spanlist上有span，这时候直接拿就行了
        // 2、k号桶上的spanlist没有span，但是>k号桶上的spanlist上有span，这时候就将这个span拆了
        // 3、k号桶上的spanlist是一个空链，并且>k号桶上的spanlist也是空链，这时候向系统申请128页的空间

        // 首先要确保k在[1, PAGE_NUM-1]这个范围中

        // 第一种情况
        if (!_spanlists[k].Empty())
        {
            // cout << "debug PageCache NewSpan end1" << endl;
            Span *span = _spanlists[k].PopFront();

            for (PageID i = 0; i < span->_page_id; i++) // 使span管理的所有的页都与span构成映射关系
            {
                // _id_span_map.set[span->_page_id + i] = span;
                // 使用基数树进行优化
                _id_span_map.set(span->_page_id + i, span);
            }

            return span;
        }

        // 第二种情况
        for (int i = k + 1; i < PAGE_NUM; i++)
        {
            if (!_spanlists[i].Empty())
            {
                Span *nspan = _spanlists[i].PopFront();
                // 将这个span拆分成两份(假如这个span是n页的)：k页空间和n-k页空间
                // 对kspan进行初始化
                // Span *kspan = new Span;
                // 用定长内存池的方式取代掉new
                Span *kspan = _span_pool.New();
                kspan->_n = k;                     // kspan管理的页数就是目标的k
                kspan->_page_id = nspan->_page_id; // kspan的pageid就是nspan的其实pageid

                // 处理nspan
                nspan->_n -= k;
                nspan->_page_id += k;

                _spanlists[nspan->_n].PushFront(nspan); // 将剩余的spanlist放到新的哈希桶中
                                                        // cout << "debug PageCache NewSpan end2" << endl;

                // 对分配完k页的nspan进行头尾映射，便于后续的合并操作
                // _id_span_map[nspan->_page_id] = nspan;
                // _id_span_map.set[nspan->_page_id + nspan->_n] = nspan;
                // 使用基数树进行优化
                cout << "debug PageCache::NewSpan 2" << endl;
                _id_span_map.set(nspan->_page_id, nspan);
                cout << "debug PageCache::NewSpan 2 mid" << endl;
                _id_span_map.set(nspan->_page_id + nspan->_n, nspan);


                for (PageID i = 0; i < kspan->_n; i++) // 使kspan的所管理的页都与kspan构建映射关系
                {
                    _id_span_map.set(kspan->_page_id + i, kspan);
                }

                return kspan;
            }
        }

        // 第三种情况
        void *ptr = SystemAlloc(PAGE_NUM - 1); // 向系统申请128页空间

        // Span *big_span = new Span;
        // 用定长内存池取代掉new
        Span *big_span = _span_pool.New();

        // 因为系统调用本身就是以页的方式申请空间，所以这里的申请的空间一定也是以页的方式进行对齐的
        big_span->_page_id = ((PageID)ptr) >> PAGE_SHIFT;
        // cout << "PageId: " << big_span->_page_id << endl;
        big_span->_n = PAGE_NUM - 1;

        _spanlists[PAGE_NUM - 1].PushFront(big_span);
        // cout << _spanlists[PAGE_NUM - 1].Begin()->_page_id << endl;
        // cout << "debug PageCache NewSpan end3" << endl;

        // 通过递归的方式，因为这里是已经来到了第三种情况，那么下次就一定会到第二种情况，然后返回
        return NewSpan(k); // 代码复用
    }
    Span *MapObjectToSpan(void *obj) // 寻找obj所对应的span
    {
        assert(obj);

        PageID pageid = ((PageID)obj) >> PAGE_SHIFT; // 得到页号

        // 这里使用了智能指针
        // 智能指针会随生命周期自动开锁,自动解锁
        // 此时不需要加锁了,因为读操作是在CentralCache::ReleaseSpanToPage中
        // 调用这个函数前已经使用了CentralCache::_mtx进行上锁了
        // std::unique_lock<std::mutex> lock(_mtx);
        // unique_lock就是这种类型在场上最多只能有一把锁
        // auto ret = _id_span_map.find(pageid);
        auto ret = _id_span_map.get(pageid);

        // if (ret != _id_span_map.end())
        if (ret != nullptr)
        {
            // 没到迭代器的结尾，说明找到了
            // return ret->second; // 将pageid对应的span返回
            return (Span *)ret; // 将pageid对应的span返回
        }
        else
        {
            // 此时没有找到
            assert(false);
            return nullptr;
        }
    }
    void ReleaseSpanToPageCache(Span *span) // 合并页
    {
        // 大于128kb的
        if (span->_n > PAGE_NUM - 1)
        {
            void *ptr = (void *)(span->_page_id << PAGE_SHIFT);

            SystemFree(ptr, span->_n); // 通过系统调用将这部分空间回收
            // delete span;//span是new出来的，所以需要手动delete掉
            // 使用定长内存池来删除span
            _span_pool.Delete(span);

            return;
        }

        // 小于128kb的
        // span所管理的范围：[span->_page_id, span->_page_id + span->_n)
        // 左合并
        while (1)
        {
            // 左邻页：span->_page_id - 1
            PageID left_id = span->_page_id - 1;
            // auto ret = _id_span_map.find(left_id);
            auto ret = _id_span_map.get(left_id);

            // 1、相邻页没有映射出对应的span
            // if (ret == _id_span_map.end())
            if (ret == nullptr)
            {
                break;
            }

            // 2、相邻页的span被CentralCache使用
            // if (ret->second->_is_use == true)
            if (((Span *)ret)->_is_use == true)
            {
                break;
            }

            // 3、相邻页的页数+当前的span页数超过128页：因为前面规定了一个span最多能管理128页
            if (((Span *)ret)->_n + span->_n > PAGE_NUM - 1)
            {
                break;
            }

            // 更新span的数据
            // span->_page_id = ret->second->_page_id;
            // span->_n += ret->second->_n;
            span->_page_id = ((Span *)ret)->_page_id;
            span->_n += ((Span *)ret)->_n;

            // 将ret->second这个span从链表中删除
            // _spanlists[ret->second->_n].Erase(ret->second);
            _spanlists[((Span*)ret)->_n].Erase((Span*)ret);
            // delete ret->second;//因为span是new出来的，所以当这个span不使用了就需要将这个span delete掉
            // 使用定长内存池来删除span
            // _span_pool.Delete(ret->second);
            _span_pool.Delete((Span*)ret);
        }

        // 右合并
        while (1)
        {
            // 右邻页：span->_page_id + span->_n
            PageID right_id = span->_page_id + span->_n;
            // auto ret = _id_span_map.find(right_id);
            auto ret = _id_span_map.get(right_id);

            // 1、相邻页没有映射出对应的span
            // if (ret == _id_span_map.end())
            if (ret == nullptr)
            {
                break;
            }

            // 2、相邻页的span被CentralCache使用
            // if (ret->second->_is_use == true)
            if (((Span*)ret)->_is_use == true)
            {
                break;
            }

            // 3、相邻页的页数+当前的span页数超过128页：因为前面规定了一个span最多能管理128页
            // if (ret->second->_n + span->_n > PAGE_NUM - 1)
            if (((Span*)ret)->_n + span->_n > PAGE_NUM - 1)
            {
                break;
            }

            // span->_n += ret->second->_n; // 合并上右邻页的管理页
            span->_n += ((Span*)ret)->_n; // 合并上右邻页的管理页

            // 将ret->second这个span从链表中删除
            // _spanlists[ret->second->_n].Erase(ret->second);
            _spanlists[((Span*)ret)->_n].Erase((Span*)ret);

            // delete ret->second;//将这个span delete 掉
            // 使用定长内存池来删除span
            _span_pool.Delete((Span*)ret);
        }

        // 合并完成后，将这个span挂到链表上
        _spanlists[span->_n].PushFront(span);
        span->_is_use = false; // 从CentralCache中回到PageCache中，此时，span就是处于一个未使用的状态

        // 映射当前span的边缘页，便于后续的合并页的操作
        //  _id_span_map[span->_page_id] = span;
        //  _id_span_map[span->_page_id + span->_n - 1] = span;
        // 使用基数树进行优化
        _id_span_map.set(span->_page_id, span);
        _id_span_map.set(span->_page_id + span->_n - 1, span);
        // cout << span->_n << endl;//test
    }

private:
    // 将默认构造函数设置为私有
    PageCache() {}
    // 将拷贝构造函数和复制构造函数删除
    PageCache(const PageCache &copy) = delete;
    PageCache &operator=(const PageCache &copy) = delete;

public:
    std::mutex _mtx; // PageCache整体的锁
private:
    SpanList _spanlists[PAGE_NUM];
    static PageCache _instance; // 单例
    // std::unordered_map<PageID, Span*> _id_span_map;//构建页与span之间的映射关系
    TCMalloc_PageMap1<32 - PAGE_SHIFT> _id_span_map; // 因为stl不支持线程安全,所以使用基数树
                                                     // 可以避免在多线程环境下
                                                     //_id_span_map在开空间的时候出现问题
    ObjectPool<Span> _span_pool;                     // span的定长内存池
};

PageCache PageCache::_instance; // 对这个单例进行初始化操作